/*
 * Change Logs:
 * Date           Author       Notes
 * 2022-01-27     tyustli          first implementation
 */

// 顺序表示的线性表

#include "sequence.h"

// 操作结果：构造一个空的顺序线性表L
void InitList(struct SqList *L)
{
    L->elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
    if (NULL == L->elem)
    {
        printf("no mem for malloc\r\n");
        return;
    }

    L->length = 0;
    L->listsize = LIST_INIT_SIZE;
}

// 初始条件：顺序线性表L已存在。操作结果：销毁顺序线性表L
void DestroyList(struct SqList *L)
{
    free(L->elem);
    L->elem = NULL;
    L->length = 0;
    L->listsize = 0;
}

// 初始条件：顺序线性表L已存在。操作结果：将L重置为空表
void ClearList(struct SqList *L)
{
    L->length = 0;
}

// 初始条件：顺序线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE
Status ListEmpty(struct SqList L)
{
    if (L.length == 0)
        return TRUE;
    else
        return FALSE;
}

// 初始条件：顺序线性表L已存在。操作结果：返回L中数据元素个数
int ListLength(struct SqList L)
{
    return L.length;
}

Status GetElem(struct SqList L, int i, ElemType *e)
{
    if (i < 1 || i > L.length)
    {
        printf("out of range\r\n");
        return ERROR;
    }

    *e = L.elem[i - 1];

    return OK;
}

// 初始条件：顺序线性表L已存在，compare()是数据元素判定函数(满足为1，否则为0)
// 操作结果：返回L中第1个与e满足关系compare()的数据元素的位序。
//           若这样的数据元素不存在，则返回值为0。
int LocateElem(struct SqList L, ElemType e, Status (*compare)(ElemType, ElemType))
{
    ElemType *p;
    int i = 1;
    p = L.elem;
    while (i <= L.length && compare(*p++, e))
        ++i;

    if (i <= L.length)
        return i;
    else
        return 0;
}

// 初始条件：顺序线性表L已存在
// 操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱，
//           否则操作失败，pre_e无定义
Status PriorElem(struct SqList L, ElemType cur_e, ElemType *pre_e)
{
    int i = 2;
    ElemType *p = L.elem + 1;
    while (i <= L.length && *p != cur_e)
    {
        p++;
        i++;
    }

    if (i > L.length)
    {
        return INFEASIBLE; // 操作失败
    }
    else
    {
        *pre_e = *--p;
        return OK;
    }
}

// 初始条件：顺序线性表L已存在
// 操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，
//           否则操作失败，next_e无定义
Status NextElem(struct SqList L, ElemType cur_e, ElemType *next_e)
{
    int i = 1;
    ElemType *p = L.elem;
    while (i < L.length && *p != cur_e)
    {
        p++;
        i++;
    }

    if (i == L.length)
    {
        return INFEASIBLE; // 操作失败
    }
    else
    {
        *next_e = *++p;
        return OK;
    }
}

// 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)+1
// 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1
Status ListInsert(struct SqList *L, int i, ElemType e)
{
    ElemType *newbase, *q, *p;

    if (i < 1 || i > L->length + 1) // i值不合法
        return ERROR;

    if (L->length >= L->listsize) // 当前存储空间已满,增加分配
    {
        if (!(newbase = (ElemType *)realloc(L->elem, (L->listsize + LIST_INCREMENT) * sizeof(ElemType))))
        {
            printf("no mem for realloc\r\n");
            return NOMEM;
        }
        L->elem = newbase;             // 新基址
        L->listsize += LIST_INCREMENT; // 增加存储容量
    }

    q = L->elem + i - 1;                           // q为插入位置
    for (p = L->elem + L->length - 1; p >= q; --p) // 插入位置及之后的元素右移
        *(p + 1) = *p;

    *q = e;      // 插入e
    ++L->length; // 表长增1

    return OK;
}

// 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)
// 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1
Status ListDelete(struct SqList *L, int i, ElemType *e)
{
    ElemType *q, *p;

    if (i < 1 || i > L->length) // i值不合法
        return ERROR;

    p = L->elem + i - 1; // p 为被删除元素的位置

    *e = *p; // 被删除元素的值赋给e

    q = L->elem + L->length - 1;
    for (++p; p <= q; ++p) // 被删除元素之后的元素左移
        *(p - 1) = *p;

    L->length--;

    return OK;
}

// 初始条件：顺序线性表L已存在
// 操作结果：依次对L的每个数据元素调用函数vi()
//           vi()的形参加'*'，表明可通过调用vi()改变元素的值
void ListTraverse(struct SqList L, void (*vi)(ElemType *))
{
    ElemType *p;
    int i;
    p = L.elem;
    for (i = 1; i <= L.length; i++)
        vi(p++);
    printf("\n");
}

/****************** end of file ********************/
